Calc's random number generator uses several methods to ensure that the numbers it produces are highly random. Knuth's Art of Computer Programming, Volume II, contains a thorough description of the theory of random number generators and their measurement and characterization.
If RandSeed has no stored value, Calc calls
Emacs' built-in random function to get a stream of
random numbers, which it then treats in various ways to avoid
problems inherent in the simple random number generators that
many systems use to implement random.
When Calc's random number generator is first invoked, it “seeds” the low-level random sequence using the time of day, so that the random number sequence will be different every time you use Calc.
Since Emacs Lisp doesn't specify the range of values that will
be returned by its random function, Calc exercises
the function several times to estimate the range. When Calc
subsequently uses the random function, it takes only
10 bits of the result near the most-significant end. (It avoids
at least the bottom four bits, preferably more, and also tries to
avoid the top two bits.) This strategy works well with the linear
congruential generators that are typically used to implement
random.
If RandSeed contains an integer, Calc uses this
integer to seed an “additive congruential” method
(Knuth's algorithm 3.2.2A, computing
‘X_n-55 -
X_n-24’). This method expands the seed value
into a large table which is maintained internally; the variable
RandSeed is changed from, e.g., 42 to the vector
‘[42]’ to
indicate that the seed has been absorbed into this table. When
RandSeed contains a vector, k r and
related commands continue to use the same internal table as last
time. There is no way to extract the complete state of the random
number generator so that you can restart it from any point; you
can only restart it from the same initial seed value. A simple
way to restart from the same seed is to type s r
RandSeed to get the seed vector, v u to unpack
it back into a number, then s t RandSeed to reseed the
generator with that number.
Calc uses a “shuffling” method as described in
algorithm 3.2.2B of Knuth. It fills a table with 13 random 10-bit
numbers. Then, to generate a new random number, it uses the
previous number to index into the table, picks the value it finds
there as the new random number, then replaces that table entry
with a new value obtained from a call to the base random number
generator (either the additive congruential generator or the
random function supplied by the system). If there
are any flaws in the base generator, shuffling will tend to even
them out. But if the system provides an excellent
random function, shuffling will not damage its
randomness.
To create a random integer of a certain number of digits, Calc builds the integer three decimal digits at a time. For each group of three digits, Calc calls its 10-bit shuffling random number generator (which returns a value from 0 to 1023); if the random value is 1000 or more, Calc throws it out and tries again until it gets a suitable value.
To create a random floating-point number with precision p, Calc simply creates a random p-digit integer and multiplies by ‘10^-p’. The resulting random numbers should be very clean, but note that relatively small numbers will have few significant random digits. In other words, with a precision of 12, you will occasionally get numbers on the order of ‘10^-9’ or ‘10^-10’, but those numbers will only have two or three random digits since they correspond to small integers times ‘10^-12’.
To create a random integer in the interval ‘[0 .. m)’, Calc counts the digits in m, creates a random integer with three additional digits, then reduces modulo m. Unless m is a power of ten the resulting values will be very slightly biased toward the lower numbers, but this bias will be less than 0.1%. (For example, if m is 42, Calc will reduce a random integer less than 100000 modulo 42 to get a result less than 42. It is easy to show that the numbers 40 and 41 will be only 2380/2381 as likely to result from this modulo operation as numbers 39 and below.) If m is a power of ten, however, the numbers should be completely unbiased.
The Gaussian random numbers generated by ‘random(0.0)’ use the “polar” method described in Knuth section 3.4.1C. This method generates a pair of Gaussian random numbers at a time, so only every other call to ‘random(0.0)’ will require significant calculations.